package com.gaogzhen.algorithm.leetCode;

/**
 * 1137. 第 N 个泰波那契数
 */
public class Tribonacci {
    public static void main(String[] args) {

        System.out.println(tribonacci3(25));
    }

    public static int tribonacci(int n) {
        if (n < 3)
            return n == 0 ? 0 : 1;
        int t0 = 0, t1 = 1, t2 = 1;
        for (int i = 3; i <= n; i++) {
            t2 = t0 + t1 + t2;
            t1 = t2 - t0 - t1;
            t0 = t2 - t0 - t1;
        }
        return t2;
    }

    public static int tribonacci1(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            int t0 = 0, t1 = 1, t2 = 1, tmp = 0;
            for (int i = 3; i <= n; i++) {
                tmp = t0 + t1 + t2;
                t0 = t1;
                t1 = t2;
                t2 = tmp;
            }
            return t2;
        }
    }

    // 空间性能优化
    public static int tribonacci2(int n) {
        if (n < 3) return n == 0 ? 0 : 1;

        int tmp, x = 0, y = 1, z = 1;
        for (int i = 3; i <= n; ++i) {
            tmp = x + y + z;
            x = y;
            y = z;
            z = tmp;
        }
        return z;
    }

    // 性能优化
    public static int tribonacci3(int n) {
        Tri t = new Tri();
        return t.nums[n];
    }
}

/**
 * 数组预存储数列
 */
class Tri {
    private int n = 38;
    public int[] nums = new int[n];
    Tri() {
        nums[1] = 1;
        nums[2] = 1;
        for (int i = 3; i < n; ++i)
            nums[i] = nums[i - 1] + nums[i - 2] + nums[i - 3];
    }
}
